Ottimizzazione Convessa: I Fondamenti dell'Approssimazione della Norma

Immagina di essere un sarto che cerca di adattare un vestito standard (l'immagine di $A$) a un cliente con proporzioni uniche (il vettore $b$). Indipendentemente da come regoli manica o vita (i coefficienti $x$), il vestito non sarà mai una perfetta vestibilità. Cerchi il "miglior" compromesso—un approssimazione della norma che minimizza la tensione o il "residuo" in ogni cucitura.

Il Quadro Matematico

L'obiettivo principale è trovare un vettore $x \in \mathbb{R}^n$ tale che la combinazione lineare $Ax = x_1a_1 + \dots + x_na_n$ approssimi al meglio $b$. Questo viene spesso indicato come la regressione di $b$ sui regressori (le colonne di $A$).

Ci concentriamo sul vettore residuo $r = Ax - b$. Nella pratica, assumiamo un sistema sovradeterminato dove $m > n$. Perché? Perché quando $m = n$ e $A$ è non singolare, il punto ottimo è semplicemente $A^{-1}b$, che produce un errore nullo—un caso banale per l'ottimizzazione.

🎯 Principio Fondamentale

Il problema di approssimazione della norma (6.1) è un problema convesso e è garantito che sia risolvibile. Esiste sempre almeno una soluzione ottimale $\hat{x}$ che minimizza la distanza tra il bersaglio e il sottospazio raggiungibile.

Variazioni Canonicali

A seconda del tipo di errore che vogliamo penalizzare, scegliamo diverse norme:

1. Minimi Quadrati ($\ell_2$ Norma)

Il metodo più comune. Minimizza la somma dei quadrati dei residui: $\|Ax - b\|_2^2$. È sensibile agli outlier estremi ma offre una soluzione analitica tramite le equazioni normali.

2. Chebyshev / Minimax ($\ell_\infty$ Norma)

Minimizza il massimo assoluto residuo $\max_i |r_i|$. Viene utilizzato quando ogni misurazione deve rimanere entro un limite rigoroso. Può essere risolto tramite il seguente programma lineare (PL):

minimizza $t$
soggetto a $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$

3. Somma dei Residui Assoluti ($\ell_1$ Norma)

Minimizza $\sum |r_i|$. Questo approccio è robusto agli outlier, poiché non eleva al quadrato gli errori. Può anche essere risolto tramite un PL:

minimizza $\mathbf{1}^T t$
soggetto a $-t \preceq Ax - b \preceq t$

Contesto di Stima

In molti campi ingegneristici, assumiamo che uno stato reale $x$ sia oscurato dal rumore: $y = Ax + v$. Il nostro obiettivo è trovare una stima $\hat{x} = \text{argmin}_z \|Az - y\|$. Scegliendo la norma, facciamo implicitamente un'ipotesi sulla distribuzione statistica del rumore $v$.

\text{Minimizza } \|u - b\| \text{ soggetto a } u \in \mathcal{A} \quad (\text{dove } \mathcal{A} = \text{Range}(A))

DOMANDA 1

Nel contesto dell'approssimazione della norma, perché assumiamo generalmente che $m > n$?

Perché se $m = n$, la soluzione è banale $x = A^{-1}b$ con residuo nullo.

Per assicurare che il problema rimanga non convesso.

Perché la norma L1 richiede più variabili che vincoli per essere risolvibile.

Per garantire che la matrice A sia sempre singolare.

DOMANDA 2

Quale formulazione di Programmazione Lineare (PL) rappresenta correttamente il problema di approssimazione di Chebyshev (minimax)?

minimizza t soggetto a -t1 ⪯ Ax - b ⪯ t1

minimizza 1ᵀt soggetto a -t ⪯ Ax - b ⪯ t

minimizza ||Ax - b||₂ soggetto a x ⪰ 0

minimizza t soggetto a Ax - b = t

DOMANDA 3

Stai calibrando un sensore e vuoi assicurarti che nessuna misurazione si discosti dal modello di più di una quantità fissa. Quale norma dovresti usare?

L∞ (Chebyshev)

L₁ (Somma dei Residui Assoluti)

L₂ (Minimi Quadrati)

La Norma di Frobenius

DOMANDA 4

Cosa è vero riguardo alla risolvibilità del problema di approssimazione della norma (6.1)?

È sempre risolvibile e convesso.

È risolvibile solo se la matrice A è simmetrica.

È non convesso se si usa la norma L1.

Non ha soluzione se il sistema è sovradeterminato.

DOMANDA 5

Nell'espressione y = Ax + v, se v rappresenta rumore di Laplace (che ha code più spesse del rumore gaussiano), quale norma di approssimazione è statisticamente più robusta?

L₁ (Somma dei Residui Assoluti)

L₂ (Minimi Quadrati)

L∞ (Chebyshev)

Pseudo-norma L₀